919E - Congruence Equation - CodeForces Solution

#include<bits/stdc++.h>

using namespace std;

int getphi(int p){
    int res = 1;
    for(int i = 2;i * i <= p;++i){
        if(p % i) continue;
        p /= i;res = res * (i - 1);
        while(p % i == 0) res = res * i, p = p / i;
    }
    if(p != 1) res = res * (p - 1);
    return res;
}
int exgcd(int a, int b, int &x, int &y)
{
    if(!b){
        x = 1; y = 0; return a;
    }
    int x0, y0, t;
    t = exgcd(b, a%b, x0, y0);
    x = y0;
    y = x0 - (a/b)*y0;
    return t;
}
int inv(int a, int p)
{
    int g, x, y;
    g = exgcd(a, p, x, y);
    if(g != 1) return -1;
    return (x%p+p)%p;
}
int add(int a, int b, int p){return a + b < p ? a + b : a + b - p;}
int sub(int a, int b, int p){return a < b ? a + p - b : a - b;}
int mul(int a, int b, int p){return 1ll * a * b % p;}
int a, b, p, na, phip, ai;
int k1, k2, gcdpp;
long long lcmpp, x;
int main()
{
    scanf("%d%d%d%lld",&a,&b,&p,&x);
    ai = b;
    na = inv(a, p);
    phip = getphi(p);
    gcdpp = exgcd(p, phip, k1, k2);
    lcmpp = 1ll * p / gcdpp * phip;
    // printf("lcmpp %lld %d %d\n",lcmpp,k1,k2);
    long long ans = 0;
    for(int i = 1;i <= phip;++i)
    {
        ai = mul(ai, na, p);
        int res = i - ai;
        // printf("%d %d\n",res,i);
        if(res % gcdpp) continue;
        // printf("ai %d res %d k1 %d p %d i %d\n",ai,res,k1,p,i);
        long long nn = (ai + 1ll*(res/gcdpp)*p%lcmpp*k1%lcmpp + lcmpp)%lcmpp;
        // printf("%lld\n",nn);
        ans += ( x / lcmpp ) + ((x % lcmpp) >= nn);
    }
    printf("%lld\n",ans);
    return 0;
}